package algorithm;

public class Leetcode134 {
    public static int canCompleteCircuit(int[] gas, int[] cost) {
        // 记录遍历的节点个数
        int count = 0;
        int len = gas.length;
        for (int i = 0;;i++) {
            // 当遍历长度为一个数组长度，则停止
            if (count == len) {
                break;
            }
            count++;

            // 遍历中以gas[i] >= cost[i]的节点作为起点
            i = i % len;
            if (gas[i] >= cost[i]) {
                // 如果i节点开始能走完一圈，则返回i
                if (canCircuitHelper(gas, cost, i)) {
                    return i;
                }
            }

        }
        return -1;
    }

    private static boolean canCircuitHelper(int[] gas, int[] cost, int i) {
        int sumGas = 0;
        int count = 0;
        int len = gas.length;
        for (int j = i; ;j++) {
            if (count == len) {
                break;
            }
            count++;

            j = j % len;
            // 当前可以加油量 - 接下来要耗费的油量
            sumGas += gas[j] - cost[j];
            // 小于0，说明不能到达下一站
            if (sumGas < 0) {
                return false;
            }
        }
        return true;
    }

    public static int canCompleteCircuit2(int[] gas, int[] cost) {
        int n = gas.length;
        int cur = 0, res = 0, ans = 0;
        for (int i = 0;i < n;i++) {
            cur += gas[i] - cost[i];
            if (cur < 0) {
                ans = i+1;
                res += cur;
                cur = 0;
            }
        }
        return cur + res >= 0 ? ans : -1;
    }


    public static void main(String[] args) {
        int[] gas  = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};
        System.out.println(canCompleteCircuit(gas, cost));

        int[] gas1  = {2,3,4};
        int[] cost1 = {3,4,3};
        System.out.println(canCompleteCircuit(gas1, cost1));
    }
}
